#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100

typedef struct 
{
    int arr[MAX_SIZE];
    int size;
}MaxHeap;
void Init_Heap(MaxHeap *heap);
void Init_Heap(MaxHeap *heap)
{
    heap->size=0;
}
void swap(int *a, int *b);
void swap(int *a, int *b) 
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
void Heapify_Up(MaxHeap *heap,int index);
void Heapify_Up(MaxHeap *heap,int index)
{
    if(index==0)
    return;
    int parent=(index-1)/2;
    if(heap->arr[parent]<heap->arr[index])
    {
        swap(&heap->arr[parent],&heap->arr[index]);
        Heapify_Up(heap,parent);
    }
}
void Heapify_Down(MaxHeap *heap,int index);
void Heapify_Down(MaxHeap *heap,int index)
{
    int left=index*2+1;
    int right=index*2+2;
    int largest = index;

    if(heap->arr[index]<heap->arr[left] && left<heap->size)
    {
        largest = left;
    }
    if(heap->arr[index]<heap->arr[right] && right<heap->size)
    {
        largest = right;
    }
    if (largest != index) 
    {
        swap(&heap->arr[index], &heap->arr[largest]);
        Heapify_Down(heap, largest);
    }
}
void Insert(MaxHeap *heap, int value);
void Insert(MaxHeap *heap, int value)
{
    if (heap->size >= MAX_SIZE) {
        printf("Heap overflow\n");
        return;
    }
    
    heap->arr[heap->size] = value;
    Heapify_Up(heap, heap->size);
    heap->size++;
}
int Extract_Max(MaxHeap *heap);
int Extract_Max(MaxHeap *heap)
{
    if (heap->size <= 0) {
        printf("Heap underflow\n");
        return -1;
    }
    
    int max_value = heap->arr[0];
    heap->arr[0] = heap->arr[heap->size - 1];
    heap->size--;
    Heapify_Down(heap, 0);
    
    return max_value;
}
int Get_Max(MaxHeap *heap);
int Get_Max(MaxHeap *heap) 
{
    if (heap->size <= 0) {
        printf("Heap is empty\n");
        return -1;
    }
    return heap->arr[0];
}
int main()
{
    int elem;
    MaxHeap H;
    Init_Heap(&H);
    Insert(&H,0);
    Insert(&H,6);
    Insert(&H,7);
    Insert(&H,2);
    Insert(&H,1);
    Insert(&H,4);
    Insert(&H,3);
    elem=Extract_Max(&H);
    printf("%d",elem);
    elem=Extract_Max(&H);
    printf("%d",elem);
}